Divide & Conquer is a general algorithmic strategy for solving complex problems with non-overlapping subproblem (for overlapping sub-problems see Dynamic Programming).
The basic strategy is to recursively brake down a problem into 2 (or more) subprobles. The solution to the original problem is then generated from the solution of the (simpler) sub-problems.
In [1]:
import Data.List
simpleSort :: (Ord a) => [a] -> [a]
simpleSort [] = []
simpleSort xs = [x_min] ++ simpleSort remainder
where
x_min = minimum xs
remainder = delete x_min xs
In [2]:
simpleSort [3, 2, 1]
In [3]:
import Test.QuickCheck
isIdempotent :: (Eq a) => (a -> a) -> a -> Bool
isIdempotent f val = (f val) == (f $ f val)
quickCheck (isIdempotent simpleSort)
isSorted :: (Ord a) => [a] -> Bool
isSorted [] = True
isSorted [_] = True
isSorted [x1, x2] = x1 <= x2
isSorted (x1:x2:xs) = (x1 <= x2) && isSorted (x2:xs)
isSorting :: (Ord a) => ([a] -> [a]) -> [a] -> Bool
isSorting f xs = isSorted $ f xs
quickCheck (isSorting simpleSort)
In [4]:
-- merges two sorted list into a larger sorted list
merge :: (Ord a) => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
| x <= y = (x:merge xs (y:ys))
| otherwise = (y:merge (x:xs) ys)
In [5]:
mergesCorrectly :: (Ord a) => ([a] -> [a] -> [a]) -> [a] -> [a] -> Bool
mergesCorrectly f xs ys = isSorted $ f (simpleSort xs) (simpleSort ys)
quickCheck (mergesCorrectly merge)
In [6]:
split :: [a] -> ([a], [a])
split [] = ([], [])
split xs = splitAt ((length xs + 1) `quot` 2) xs
quickCheck (\xs -> uncurry (++) (split xs) == xs)
In [36]:
mergeSort :: (Ord a) => [a] -> [a]
mergeSort [] = []
mergeSort xs
| length xs <= 10 = simpleSort xs
| otherwise = merge (mergeSort left) (mergeSort right)
where (left, right) = split xs
In [45]:
quickCheck (isIdempotent mergeSort)
quickCheck (isSorting mergeSort)